package 图.无向图;

import 抽象数据类型.Bag;

/**
 * @description:
 * @author: ywk 通过union-find ,实现查找图的联通分量
 * @date: 2021-07-31
 */
public class 找出图的联通分量UF {
    public static void main(String[] args) {
        int[] arr1 = {0, 1, 2, 0, 3, 4, 5, 6, 7, 9, 10, 11, 12};
        int[] arr2 = {6, 0, 0, 5, 5, 3, 4, 4, 8, 11, 9, 12, 9};
        UF uf = new UF(arr1.length);
        for (int i = 0; i < arr1.length; i++) {
            uf.connect(arr1[i], arr2[i]);
        }
        Bag<Integer>[] components = new Bag[arr1.length];
        for (int i = 0; i < components.length; i++) {
            components[i] = new Bag<>();
        }
        for (int i = 0; i < arr1.length; i++) {
            components[uf.find(i)].add(i);
        }
        for (int i = 0; i < components.length; i++) {
            if (!components[i].isEmpty()) {
                System.out.println(i + ">>");
                for (Integer integer : components[i]) {
                    System.out.print(integer + "\t");

                }
                System.out.println();
            }
        }
    }

    public static class UF {
        public int[] id;
        public int[] size;//每棵最深树的高度
        public int count;
        public UF(int N) {
            count = N;
            id = new int[N];
            size = new int[N];
            for (int i = 0; i < N; i++) {
                id[i] = i;//只连自己
            }
            for (int i = 0; i < N; i++) {
                size[i] = 1;//每棵树的高度起始为1
            }
        }

        public boolean connected(int index1, int index2) {
            return find(index1) == find(index2);
        }

        public void connect(int index1, int index2) {
            int p = find(index1);
            int q = find(index2);
            if (p == q) {
                return;
            }
            if (size[p] < size[q]) {
                size[q] += size[p];
                id[p] = q;
            } else {
                size[p] += size[q];
                id[q] = p;
            }
            count--;
        }

        public int find(int index1) {
            while (index1 != id[index1]) {
//                id[index1] = id[id[index1]]; //路径压缩
                index1 = id[index1];
            }
            return index1;
        }
    }
}
